package data_structure.interview_questions;

/**
 * 面试题：
 * 1.求单链表中结点的数量
 * 2.查找单链表中倒数第k个结点【新浪面试题】
 * 3.单链表的反转【腾讯面试题】
 */
class LinkedListCountDemo {
    public static void main(String[] args) {
        Student s1 = new Student(1);
        Student s2 = new Student(2);
        Student s3 = new Student(3);
        Student s4 = new Student(4);
        LinkedList list = new LinkedList();
        list.add(s1);
        list.add(s2);
        list.add(s3);
        list.add(s4);
        System.out.println("统计数量: "+list.selectCount());
        try {
            System.out.println(list.selectIndex(6));
        }catch (Exception e) {
            System.out.println(e);
        }
        //测试 单链表反转
        System.out.println("原来链表情况~");
        list.select();
        System.out.println("反转单链表~");
        list.reverseList();
        list.select();
    }
}

class LinkedList{
    //头结点
    private static Student head = new Student(0);

    //遍历单链表
    public void select(){
        Student temp = head.next;
        while (temp != null){
            System.out.println(temp);
            temp = temp.next;
        }
    }

    //3.单链表的反转【腾讯面试题】
    public void reverseList(){
        if (head.next == null || head.next.next == null)
            return;
        Student temp = head.next;
        Student reverseHead = new Student(0);
        Student temp2 = null;
        //遍历链表，没遍历一个结点 就取出，放在新链表的第一个
        while (temp != null){
            //(问题) -> reverseHead.next = temp
            temp2 = temp.next;
            //第一次 reverseHead 为空
            temp.next = reverseHead.next;//将temp下一个结点指向新链表的最前端
            reverseHead.next = temp;
            temp = temp2;
        }
        //将head.next指向reverseHead.next实现反转
        head.next = reverseHead.next;
    }

    // 2.查找单链表中倒数第k个结点【新浪面试题】
    public Student selectIndex(int n){
        //第一步求长度
        int len = selectCount();
        if ((len - n) < 0) throw new RuntimeException("不存在当前位置");
        Student temp = head;
        int count = 0;
        while (count<(len-n+1)){
            temp=temp.next;
            count++;
        }
        return temp;
    }

    //添加数据
    public void add(Student student){
        Student temp = head;
        while (temp.next != null){
            temp = temp.next;
        }
        temp.next = student;
    }

    //1.求单链表中结点的数量
    public static int selectCount(){
        int count = 0;
        Student temp = head;
        while (temp.next != null){
            count++;
            temp = temp.next;
        }
        return count;
    }
}

class Student{
    private int id;
    Student next;

    public Student(int id) {
        this.id = id;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    @Override
    public String toString() {
        return "Student{" +
                "id=" + id +
                '}';
    }
}
